package rbtree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-09-04
 * Time: 20:48
 */
public class RBTree {
    static class RBTreeNode {
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode parent;
        public int val;
        public COLOR color;//枚举

        public RBTreeNode(int val) {
            this.val = val;

            //新创建的节点默认是红色
            this.color = COLOR.RED;
        }
    }
    public RBTreeNode root;

    //插入：
    public boolean insert(int val) {
        RBTreeNode node = new RBTreeNode(val);

        if (root == null) {
            root = node;
            //插入节点默认为红色所有，当root为空时，要把插入的节点变为黑色
            root.color = COLOR.BLACK;
            return true;
        }

        RBTreeNode cur = root;
        RBTreeNode parent = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                return false;
            }
        }

        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }

        node.parent = parent;
        cur = node;//指向新插入的节点

        //开始调整颜色
        while (parent != null && parent.color == COLOR.RED) {
            RBTreeNode grandParent = parent.parent;

            /**情况一：
             *
             * cur为红，p为红，g为黑，uncle存在且为红
             *
             *  parent在grandParent左边，uncle在grandParent右边
             */
            if (parent == grandParent.left) {
                RBTreeNode uncle = grandParent.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;

                    //预防grandParent的父亲为红色，就还有子树,继续向上修改
                    cur = grandParent;
                    parent = cur.parent;
                } else {

                    /**
                     * 情况三：
                     * 先左单旋parent
                     * 再交换parent和cur的引用,变成情况二处理
                     */
                    if (parent.right == cur) {
                        rotateLeft(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;

                    }//变成情况二


                    /** 情况二：
                     * cur为红，p为红，g为黑，uncle为黑色，或者uncle不存在
                     *
                     *  方法：
                     *  1.先右单旋
                     *  2.再改颜色
                     */

                    rotateRight(grandParent);

                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                }
            } else {


                //下面情况和上面情况完全相反


                //parent == grandParent.right
                RBTreeNode uncle = grandParent.left;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;

                    //预防grandParent的父亲为红色，就还有子树,继续向上修改
                    cur = grandParent;
                    parent = cur.parent;
                } else {

                    if (parent.left == cur) {
                        rotateRight(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;

                    }
                    //变成情况二

                    rotateLeft(grandParent);
                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                }
            }
        }

        //当parent为空时，要把根节点变为黑色
        root.color = COLOR.BLACK;
        return true;
    }


        /**
         * 右单旋
         * @param parent
         */
        private void rotateRight (RBTreeNode parent){
            RBTreeNode subL = parent.left;
            RBTreeNode subRL = subL.right;

            parent.left = subRL;
            subL.right = parent;
            //如果旋转的整棵树也是一个子树，记录下原来该树的父亲，后续修改
            RBTreeNode pParent = parent.parent;

            if (subRL != null) {
                subRL.parent = parent;
            }
            parent.parent = subL;

            //看看整棵树是否也是一个子树
            if (parent == root) {
                root = subL;
                root.parent = null;
            } else {
                //是子树就确定这棵树是左子树还是右子树
                if (pParent.left == parent) {
                    pParent.left = subL;
                } else {
                    pParent.right = subL;
                }
            }
            subL.parent = pParent;

        }

        /**
         * 左单旋
         * @param parent
         */
        private void rotateLeft (RBTreeNode parent){
            RBTreeNode subR = parent.right;
            RBTreeNode subRL = subR.left;

            parent.right = subRL;
            subR.left = parent;
            RBTreeNode pParent = parent.parent;

            if (subRL != null) {
                subRL.parent = parent;
            }
            parent.parent = subR;

            //看看整棵树是否也是一个子树
            if (parent == root) {
                 root = subR;
                root.parent = null;
            } else {
                //是子树就确定这棵树是左子树还是右子树
                if (pParent.left == parent) {
                    pParent.left = subR;
                } else {
                    pParent.right = subR;
                }
            }
            subR.parent = pParent;
        }



    /**
     * 红黑树的验证：
     */


    /**1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
     * 中序遍历：
     * @param root
     */
    public void inorder(RBTreeNode root){
        if(root == null){
            return;
        }

        inorder(root.left);
        System.out.print(root.val+ " ");
        inorder(root.right);
    }


    //2.检测其是否满足红黑树的性质:
    public boolean isRBTree(){
        if(root == null){
            //空树也是红黑树
            return true;
        }

        if(root.color != COLOR.BLACK){
            System.out.println("违反了性质2：根节点不是黑色");
            return false;
        }


        RBTreeNode cur = root;
        //blackNum是事先计算好一边黑色节点的个数
        int blackNum = 0;
        while (cur != null){
            if (cur.color == COLOR.BLACK){
                blackNum++;
            }
            cur = cur.left;

        }
        //判断性质三有没有两个红色的节点 && 判断性质四：每条路径的黑色节点个数是否相等
        return checkRedColor(root) && checkBlackNum(root,blackNum,0);
    }

    /**
     * 判断性质三有没有两个红色的节点：
     * 思路：遍历当前二叉树节点如果是红色，则判断他的父亲节点是不是红色
     * @param root
     * @return
     */
    private boolean checkRedColor(RBTreeNode root){
        if(root == null){
            return true;
        }

        if (root.color == COLOR.RED){
            RBTreeNode parent = root.parent;
            if (parent != null && parent.color == COLOR.RED){
                System.out.println("违反了性质三: 连续出现两个红色的节点");
                return false;
            }
        }
       return checkRedColor(root.left) && checkRedColor(root.right);
    }


    /**
     *判断性质四：每条路径的黑色节点个数是否相等
     * @param root
     * @param blackNum:事先计算好黑色节点的个数
     * @param pathBlackNum：每次递归计算的黑色节点的个数
     * 思路：看 blackNum 和 pathBlackNum 的数量是否相等
     * @return
     */
    private boolean checkBlackNum(RBTreeNode root,int blackNum, int pathBlackNum){
        if(root == null){
            return true;
        }

        if (root.color == COLOR.BLACK){
            pathBlackNum++;
        }

        //blackNum 和 pathBlackNum 的数量是否相等就不满足性质
        if (root.left == null && root.right == null){
            if(pathBlackNum != blackNum){
                System.out.println("违反了性质四：每条路径的黑色节点个数不相等了！");
                return false;
            }
        }
        return checkBlackNum(root.left,blackNum,pathBlackNum)
                && checkBlackNum(root.right,blackNum,pathBlackNum);
    }
}

